home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / sml_nj / 93src.lha / src / util / strghash.sml < prev    next >
Encoding:
Text File  |  1993-01-27  |  946 b   |  44 lines
  1. (* Copyright 1989 by AT&T Bell Laboratories *)
  2. (* util/strghash.sml *)
  3.  
  4. structure StrgHash =
  5. struct
  6.  
  7.   val prime = 8388593 (* largest prime less than 2^23 *)
  8.   val base = 128
  9.  
  10. (* the simple version --
  11.     fun hashString(str: string) : int =
  12.         let fun loop (0,n) = n
  13.           | loop (i,n) = 
  14.               let val i = i-1
  15.               val n' = (base * n + ordof(str,i)) 
  16.            in loop (i, (n' - prime * (n' quot prime)))
  17.           end
  18.      in loop (size str,0)
  19.     end
  20. *)
  21.  
  22.   fun hashString(str: string) : int =
  23.       let val l = size str
  24.        in case l
  25.         of 0 => 0
  26.          | 1 => ord str
  27.          | 2 => ordof(str,0) + base * ordof(str,1)
  28.          | 3 => ordof(str,0) + base * (ordof(str,1) + base * ordof(str,2))
  29.          | _ =>
  30.         let fun loop (0,n) = n
  31.               | loop (i,n) = 
  32.               let val i = i-1
  33.                   val n' = (base * n + ordof(str,i)) 
  34.                in loop (i, (n' - prime * (n' quot prime)))
  35.               end
  36.          in loop (l,0)
  37.         end
  38.       end
  39.  
  40. end (* structure StrgHash *)
  41.  
  42.  
  43.  
  44.